/**
 * 循环队列
 *
 * @author Kevin
 * @date 2018-11-20
 */
public class LoopQueue<E> implements Queue<E> {

    /**
     * 数据
     */
    private E[] data;

    /**
     * 队头和队尾
     */
    private int front, tail;

    /**
     * 队列大小
     */
    private int size;

    public LoopQueue() {
        this(10);
    }

    public LoopQueue(int capacity) {
        // 多出一个位置
        this.data = (E[]) new Object[capacity + 1];
        this.front = 0;
        this.tail = 0;
        this.size = 0;
    }

    @Override
    public int getSize() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
        return this.front == this.tail;
    }

    @Override
    public void enqueue(E e) {
        if ((this.tail + 1) % this.data.length == this.front) {
            resize(getCapacity() * 2);
        }

        data[this.tail] = e;
        this.tail = (this.tail + 1) % this.data.length;
        this.size++;
    }

    @Override
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
        }

        E result = this.data[this.front];
        this.data[this.front] = null;
        this.front = (this.front + 1) % this.data.length;
        this.size--;

        if (this.size == getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }

        return result;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Queue is empty.");
        }

        return this.data[this.front];
    }

    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity + 1];

        for (int i = 0; i < this.size; i++) {
            newData[i] = this.data[(i + this.front) % this.data.length];
        }

        this.data = newData;
        this.front = 0;
        this.tail = this.size;
    }

    public int getCapacity() {
        return this.data.length - 1;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("Queue: size = %d, capacity=%d\n", this.size, getCapacity()));
        sb.append("front [");

        for (int i = this.front; i != this.tail; i = (i + 1) % this.data.length) {
            sb.append(this.data[i]);
            if ((i + 1) % this.data.length != this.tail) {
                sb.append(", ");
            }
        }

        sb.append("] tail");

        return sb.toString();
    }
}
